
//994.腐烂的橘子
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        //多源BFS问题
        int n=grid.size(),m=grid[0].size();
        int dx[]={0,0,-1,1};
        int dy[]={1,-1,0,0};

        //先将所有腐烂的桔子入队列
        queue<pair<int,int>> q;
        int fine=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(grid[i][j]==1) fine++;
                else if(grid[i][j]==2) q.push({i,j});
            }
        }
        if(fine==0) return 0;
        //从每个腐烂的桔子位置开始向外进行BFS
        int step=0;
        while(!q.empty())
        {
            int _size=q.size();
            step++;
            for(int i=0;i<_size;i++)
            {
                int x=q.front().first,y=q.front().second;
                q.pop();
                for(int k=0;k<4;k++)
                {
                    int a=x+dx[k],b=y+dy[k];
                    if(a>=0&&a<n&&b>=0&&b<m&&grid[a][b]==1)
                    {
                        if(--fine==0) return step;   //已经没有好橘子了
                        grid[a][b]=2;           //将改新鲜橘子标记为腐烂
                        q.push({a,b});
                    }
                }
            }
        }
        return -1;
    }
};


